package 极客算法训练营.chapter06;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 二叉树的前序遍历 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    class Solution1 {
        private List<Integer> res = new ArrayList<>();

        public List<Integer> preorderTraversal(TreeNode root) {
            recursionTree(root);
            return res;
        }

        public void recursionTree(TreeNode node) {
            //递归终止条件
            if (node == null) return;
            //递归执行体
            res.add(node.val);
            recursionTree(node.left);
            recursionTree(node.right);
        }
    }

    class Solution2 {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) return res;
            Deque<TreeNode> stack = new LinkedList<>();
            while (root != null || !stack.isEmpty()) {
                //可以深入遍历
                while (root != null) {
                    res.add(root.val);
                    stack.push(root);
                    root = root.left;
                }
                //需要从深处回调
                TreeNode pop = stack.pop();
                root = pop;
                root = root.right;
            }
            return res;
        }
    }

    /**
     * Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：
     * <p>
     * 新建临时节点，令该节点为 root；
     * <p>
     * 如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
     * <p>
     * 如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
     * <p>
     * 如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。
     * 当前节点更新为当前节点的左子节点。
     * <p>
     * 如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
     * <p>
     * 重复步骤 2 和步骤 3，直到遍历结束。
     */
    class Solution3 {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) return res;
            while (root != null) {
                if (root.left != null) {
                    //左子树不为空时,先找到它在中序遍历时的前驱
                    TreeNode predecessor = root.left;
                    while (predecessor.right != null && predecessor.right != root) {
                        predecessor = predecessor.right;
                    }
                    //若前驱结点为空建立连接，若不为空断开连接
                    if (predecessor.right == null) {
                        predecessor.right = root;
                        res.add(root.val);
                        root = root.left;
                    } else {
                        predecessor.right = null;
                        root = root.right;
                    }
                } else {
                    //左子树为空时
                    res.add(root.val);
                    root = root.right;
                }
            }
            return res;
        }
    }
}
